package com;

/**
 * @author 罗俊华
 * @date 2021/7/23 - 10:46 上午
 */
public class JumpGame {

    public static void main(String[] args) {
        int[] array = {2, 3, 1, 1, 4};
        int jump = new JumpGame().jump(array);
        System.out.printf("最少要跳 %s 步", jump);
    }

    public int jump(int[] nums) {

        if (nums.length - 2 < 0) {
            return 0;
        }

//        int[] cache = new int[nums.length];
        return searchPath(nums, /*cache,*/ nums.length - 1);
    }


    private int searchPath(int[] nums, /*int[] cache,*/ int currentIndex) {

        int minStepIndex = currentIndex;

//        当从原点可以跳到当前节点时，就结束了
        if (nums[0] >= currentIndex) {
            return 1;
        }

        for (int i = currentIndex; i > 0; i--) {

            if (nums[i] >= currentIndex - i) {
                minStepIndex = Math.min(minStepIndex, i);
            }
        }

        return 1 + searchPath(nums,/* cache,*/ minStepIndex);

    }
}
